#include <iostream>
#include <vector>
#include <utility>
#include <limits>
#include "math.h"
#include "conio.h"

using namespace std;

const int big_value = 10000;

int get_minimal_time_to_collect_all_coins(const vector<pair<int,int>> &pos_and_time)
{
	vector<vector<int>> t_left(pos_and_time.size()),
		t_right(pos_and_time.size());

	for (int i_coin = 0; i_coin < pos_and_time.size(); ++i_coin)
	{
		t_left[i_coin].resize(pos_and_time.size(), big_value);
		t_right[i_coin].resize(pos_and_time.size(), big_value);
	}

	for (int r = 0; r < pos_and_time.size(); ++r)
	{
		for (int l = r; l >= 0; --l)
		{
			if (r == l)
			{
				t_left[l][r] = 0;
				t_right[l][r] = 0;
			}
			else
			{
				int best_left_end = min( t_left[l+1][r] + abs(pos_and_time[l].first - pos_and_time[l+1].first),
					t_right[l+1][r] + abs(pos_and_time[l].first - pos_and_time[r].first));

				int best_right_end = min( t_right[l][r-1] + abs(pos_and_time[r-1].first - pos_and_time[r].first),
					t_left[l][r-1] + abs(pos_and_time[l].first - pos_and_time[r].first));

				if (t_left[l][r] > best_left_end)
					t_left[l][r] = best_left_end;

				if (t_right[l][r] > best_right_end)
					t_right[l][r] = best_right_end;

				if (t_left[l][r] > pos_and_time[l].second)
					t_left[l][r] = big_value;

				if (t_right[l][r] > pos_and_time[r].second)
					t_right[l][r] = big_value;
			}
		}
	}

	int best_time = min(t_left[0][pos_and_time.size()-1], t_right[0][pos_and_time.size()-1]);
	return best_time;
}

void main()
{
	int n_coins;
	cout << "Input the number of coins:" << endl;
	cin >> n_coins;

	cout << "Input coins' positions and time:" << endl;
	vector<pair<int,int>> pos_and_time(n_coins);
	for (int i_coin = 0; i_coin < n_coins; ++i_coin)
	{
		int dist, time;
		cin >> dist >> time;
		pos_and_time[i_coin] = make_pair(dist, time);
	}
	cout << "Minimal time to collect all coins: " << get_minimal_time_to_collect_all_coins(pos_and_time) << endl;
	_getch();
}